#include <iostream>
#include <stdexcept>

template <typename T>
class my_list   // 双向链表 
{
private:
    struct Node
    {
        T data;
        Node* prev;
        Node* next;
        Node(const T& value):data(value),prev(nullptr),next(nullptr){}
    };
    Node* head; // 存数据
    Node* tail;
    size_t m_size;
    
public:
    class iterator
    {
    private:
        Node* current;
        friend class my_list<T>;
    public:
        iterator(Node* node = nullptr):current(node){} //默认构造函数

        T& operator*(){
            if(current == nullptr) throw std::out_of_range("dereferencing end iterator");
            return current->data;
        }

        //前缀自增/减
        iterator& operator++()
        {
            if(current == nullptr) throw std::out_of_range("iterator is nullptr");
            current = current->next;
            return *this;
        }

        iterator& operator--()
        {
            if(current == nullptr) {
                throw std::out_of_range("iterator is nullptr");
            }
            if(current->prev == nullptr) throw std::out_of_range("front itetator is nullptr");
            current = current->prev;
            return *this;
        }

        //后缀自增/减
        iterator operator++(int)
        {
          iterator temp = *this;   //保存当前状态
          ++(*this);
          return temp;
        }
        iterator operator--(int)
        {
          iterator temp = *this;   //保存当前状态
          --(*this);
          return temp;
        }

        //比较相等
        bool operator==(const iterator& other) const {return current == other.current;}
        bool operator!=(const iterator& other) const {return current != other.current;}

    };

    //迭代器接口
    iterator begin(){return iterator(head);}

    iterator end(){return iterator(nullptr);}

    iterator insert(iterator pos, const T& num)
    {
        Node* new_node = new Node(num);   //创建新节点
        
        if (pos.current == nullptr) {
            // 在末尾插入
            if (tail == nullptr) {
                head = tail = new_node;
            } else {
                tail->next = new_node;
                new_node->prev = tail;
                tail = new_node;
            }
        } else {
            new_node->prev = pos.current->prev;
            new_node->next = pos.current;
            if(pos.current->prev != nullptr) { //前面有节点
                pos.current->prev->next = new_node;
            } else {
                head = new_node;
            }
            pos.current->prev = new_node;
        }
        ++m_size;
        return iterator(new_node);
    }

    iterator erase(iterator pos)
    {
        if(empty()){
            throw std::out_of_range("list is empty");
        }
        if (pos.current == nullptr) {
            throw std::out_of_range("iterator is a nullptr");
        }
        
        Node* next_node = pos.current->next;    //保存删除节点的下一个节点
        
        if (pos.current->prev != nullptr) {
            pos.current->prev->next = pos.current->next;
        } else {
            head = pos.current->next;
        }
        
        if (pos.current->next != nullptr) {
            pos.current->next->prev = pos.current->prev;
        } else {
            tail = pos.current->prev;
        }

        delete pos.current;
        --m_size;
        return iterator(next_node); //返回下一节点
    }
   
    my_list():head(nullptr),tail(nullptr),m_size(0){} // 默认构造函数

    ~my_list()
    {
        clear();
    }

    void push_back(const T& value)  // 尾插
    {
        Node* new_node = new Node(value); // 创建新节点
        
        if(tail == nullptr) {    // 如果链表为空
            head = tail = new_node;
        } else {
            tail->next = new_node;  //尾节点的next = 新节点的地址
            new_node->prev = tail;  //新节点的prev = 尾节点
            tail = new_node;        //尾节点 = 新节点的地址
        }
        m_size++;
    }
    
    void push_front(const T& value) //头增
    {
        Node* new_node = new Node(value); // 创建新节点
        
        if(head == nullptr) {    // 如果链表为空
            head = tail = new_node;
        } else {
            head->prev = new_node;  //头节点的prev = 新节点的地址
            new_node->next = head; //新节点的next = 头节点
            head = new_node;        //头节点 = 新节点的地址
        }
        m_size++;
    }
    
    void pop_back() // 尾删
    {
        if(empty()) throw std::out_of_range("list is empty");
        
        if(head == tail) {   // 如果只有一个节点
            delete head;
            head = tail = nullptr;
        } else {
            Node* temp = tail;  //temp存储尾节点
            tail = tail->prev;  //尾节点 = 尾节点的prev
            tail->next = nullptr;   //尾节点的next为空
            delete temp;    //释放内存
        }
        m_size--;
    }
    
    void pop_front()    //头删
    {
        if(empty()) throw std::out_of_range("list is empty");
        
        if(head == tail) {   // 如果只有一个节点
            delete head;
            head = tail = nullptr;
        } else {
            Node* temp = head;  //temp存储头节点
            head = head->next;  //头节点 = 头节点的next
            head->prev = nullptr;   //头节点的prev为空
            delete temp;    //释放内存
        }
        m_size--;
    }
    T& front() const {
        return head->data;
    }


    bool empty() const { return m_size == 0; }
    
    void clear()
    {
        Node* current = head;
        while(current != nullptr) {
            Node* next = current->next;
            delete current;
            current = next;
        }
        head = tail = nullptr;
        m_size = 0;
    }
    
    size_t size() const { return m_size; }
};